package oj;

public class LC92 {
    //穿针引线(一次遍历)  头插法
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head==null || head.next==null) return head;
        ListNode dummyHead=new ListNode(-1);
        dummyHead.next=head;
        ListNode prev=dummyHead;
        for(int i=0;i<left-1;i++){
            prev=prev.next;
        }
        ListNode cur=prev.next;
        ListNode next;
        //头插法 反转链表
        for(int i=0;i<right-left;i++){
            next=cur.next;
            cur.next=next.next;
            next.next=prev.next;
            prev.next=next;
        }
        return dummyHead.next;
    }

    //穿针引线(两次遍历)
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if(head==null || head.next==null) return head;
//        ListNode dummyHead=new ListNode(-1);
//        dummyHead.next=head;
//        ListNode prev=dummyHead;
//        for(int i=0;i<left-1;i++){
//            prev=prev.next;
//        }
//        ListNode rightNode=prev;
//        for(int i=0;i<right-left+1;i++){
//            rightNode=rightNode.next;
//        }
//        ListNode next=rightNode.next;
//        ListNode leftNode=prev.next;
//
//        prev.next=null;
//        rightNode.next=null;
//
//        reverse(leftNode);
//
//        prev.next=rightNode;
//        leftNode.next=next;
//        return dummyHead.next;
//
//    }
//
//    private void reverse(ListNode node){
//        ListNode prev=null;
//        ListNode cur=node;
//
//        while(cur!=null){
//            ListNode next=cur.next;
//            cur.next=prev;
//            prev=cur;
//            cur=next;
//        }
//    }
}
